package labirynthPackage;

/**
 *
 * @author Biserova Ekaterina, Baburkina Anastasia, Perminov Alexander
 */

import java.io.*;
import java.util.LinkedList;

public class Field{
    public Point[] prizes;
    /**
     * Размеры массива и количество призов на карте
     */
    final public int height, width, numOfL;
    /**
     * Координаты выхода
     */
    public Point exit;
    /**
     * Конструктор класса Field с параметром - именем файла
     * Это имя файла используется, чтобы заполнить массив area
     * @param fileName - имя файла, где хранится карта
     */
    /**
     * Начальные координаты робота
     */
    final public Point robotPos; 
    /**
     * Двумерный массив, каждый элемент которого - ячейка особого типа в соответствии с символом на карте
     */
    private CellType area [][];
    /**
     * Конструктор поля. Считывает из файла массив, заполняет все возможные поля
     * @param fileName - имя файла с массивом
     * @throws IOException 
     */
    public Field(String fileName) throws IOException {
        InputStream obj = System.in;
        int numerL = 0;
        int heightArr = 0;
        int widthArr = 0;
        int currentWidthArr = 0;
        Point robotPos1 = new Point(0,0); 
        char c = (char) obj.read();
        obj.mark(0);
        for (int i = 0;  obj.available()!=0; i++) {
            if (c == '\n') {
                heightArr++;
                currentWidthArr = 0;
            } else {
                currentWidthArr++;
                //Ширина массива - наибольшее из всех длин строк
                if (currentWidthArr > widthArr) {
                    widthArr = currentWidthArr;
                }
            }
            if (c == '\\') {
                numerL++;
            }
            if (c == 'R') {
                robotPos1 = new Point(heightArr, currentWidthArr-1);
            }
            //System.out.print(c);
            c = (char) obj.read();
        }
        if (robotPos1.x != 0 && robotPos1.y != 0) {
                robotPos = new Point(robotPos1.y,robotPos1.x);
        }
        else {
            robotPos = new Point(0,0);
        }
        /*
        //Выводим количество призов, высоту и ширину массива
        System.out.println();
        System.out.print("numOfL:"+numerL);
        System.out.println();
        System.out.print("heightArr:" + (heightArr+1));
        System.out.println();
        System.out.print("widthArr:" + (widthArr));
        System.out.println();
        System.out.print("Robot Coords: " + robotPos.x + ' ' + robotPos.y);
        System.out.println();
        */
        obj.reset();
        
        numOfL=numerL;
        height=heightArr+1;
        width=widthArr;
        area = new CellType[height][width];
        
        //Объявляем массив, где храним координаты всех лямбд, и его счетчик
        // Нумеруем с единицы, чтобы не запутаться с индексами при создании массива с соответсвием ребер и вершин
        int k = 1;
        prizes = new Point[numerL+1];
        prizes[0] = new Point(0,0);
        
        //Заполняем массив в соответствии с картой
        area[height-1][width-1]=CellType.Wall; //последний элемент
            for (int a = 0; a < height; a++) {
                widthLoop:
                for (int b = 0; b <= width; b++) {
                    if (obj.available()==0) {
                        return;
                    }
                    char d=(char)obj.read();
                    switch(d){
                    case'\n':{
                        for(int f=b-1; f<width; f++){
                            if(f<0){
                                f++;
                            }
                            if(area[a][f]!=CellType.Close){
                                area[a][f]=CellType.Wall;
                            }
                            //System.out.print(area[a][f].name());
                        }
                        //System.out.println();
                        break widthLoop;
                    }
                    case '#': {
                        area[a][b]=CellType.Wall;
                        //System.out.print(area[a][b].name());
                        break;
                    }
                    case '\\': {
                        area[a][b]=CellType.A;
                        prizes[k++] = new Point(a,b);
                        //System.out.print(area[a][b].name());
                        break;
                    }
                    case '.': {
                        area[a][b]=CellType.Ground;
                        //System.out.print(area[a][b].name());
                        break;
                    }
                    case ' ': {
                        area[a][b]=CellType.Empty;
                        //System.out.print(area[a][b].name());
                        break;
                    }
                    case '*': {
                        area[a][b]=CellType.Stone;
                        //System.out.print(area[a][b].name());
                        break;
                    }
                    case 'L': {
                        area[a][b]=CellType.Close;
                        //System.out.print(area[a][b].name());
                        exit = new Point(a,b);
                        break;
                    }
                    case 'R': {
                        area[a][b]=CellType.Empty;
                        //System.out.print(area[a][b].name());
                        break;
                    }
                    default:break;
                    }
                }
            }
            obj.close();
        //}
    };    
    /**
     * Метод поиска пути из начальной в конечную точку
     * @param start - начальная точка
     * @param finish - конечная точка
     * @return way - строка с последовательностью команд для перемещения робота, либо символ Z, если в процессе нас заваливает камнями
     */
    public String AStar(Point start, Point finish){
        // Создадим все нужные списки
        //"открытый список" клеток, которые нужно обработать
        LinkedList<Point> openList = new LinkedList<>();
        // "закрытый список" клеток, которые больше не нужно проверять
        LinkedList<Point> closedList = new LinkedList<>();
        //временный список
        LinkedList<Point> tmpList = new LinkedList<>();
        
        // Стартовая и конечная
        start.setAsStart();
        finish.setAsFinish();
        
        boolean isFirstIteration=true;
        
        String way = "";
        //Если робот уже стоит в клетке, куда его отправили - возвращаем пустую строку
        if(start.x==finish.x & start.y==finish.y){
            return way;
        }
        boolean found = false;

        // Добавляем стартовую клетку в открытый список.
        openList.push(start);

        //Пока маршрут не найден
        while (!found) {
            // Ищем в открытом списке клетку с наименьшей стоимостью F. Делаем ее текущей клеткой.
            Point min = openList.getFirst();
            for (Point cell : openList) {
                if (cell.F < min.F) {
                    min = cell;
                }
            }

            // Помещаем ее в закрытый список. (И удаляем с открытого)
            closedList.push(min);
            openList.remove(min);

            // Для каждой из соседних 4-х клеток ...
            tmpList.clear();
            
            if(min.x-1>=0){
                Point p = new Point(min.y, min.x - 1);
                if(checkDeath(Direction.Left, min, isFirstIteration)){
                    p.G=999999;
                }
                tmpList.add(p);
            }
            if(min.y+1<height){
                Point p = new Point(min.y + 1, min.x);
                if(checkDeath(Direction.Down, min, isFirstIteration)){
                    p.G=999999;
                }
                tmpList.add(p);
            }
            if(min.x+1<width){
                Point p = new Point(min.y, min.x + 1);
                if(checkDeath(Direction.Right, min, isFirstIteration)){
                    p.G=999999;
                }
                tmpList.add(p);
            }
            if(min.y-1>=0){
                Point p = new Point(min.y - 1, min.x);
                if(checkDeath(Direction.Up, min, isFirstIteration)){
                    p.G=999999;
                }
                tmpList.add(p);
            }
   
            isFirstIteration=false;
                    
            for (Point neightbour : tmpList) {
                //Если клетка непроходимая или она находится в закрытом списке, игнорируем ее. В противном случае делаем следующее.
                if (getCell(neightbour)==CellType.Wall || getCell(neightbour)==CellType.Close || closedList.contains(neightbour)) {
                    continue;
                }
                //Проверка, есть ли возможность подвинуть камень
                int t = neightbour.x-min.x;
                if(neightbour.x+t>=0 & neightbour.x+t<width){
                    if (getCell(neightbour)==CellType.Stone){
                        if(t==0 | (area[neightbour.y][neightbour.x+t]!=CellType.Empty)) {
                            continue;
                        }else if(area[neightbour.y][neightbour.x+t]==CellType.Empty & (area[neightbour.y][neightbour.x+t+t]==CellType.Close |area[neightbour.y][neightbour.x+t+t]==CellType.Open)){
                            //Причём на выход мы его не двигаем                
                            continue;
                        }
                    }
                }
                
                //Если клетка еще не в открытом списке, то добавляем ее туда. 
                //Делаем текущую клетку родительской для это клетки. Расчитываем стоимости F, G и H клетки.
                if (!openList.contains(neightbour)) {
                    openList.add(neightbour);
                    neightbour.parent = min;
                    neightbour.H = neightbour.mandist(finish);
                    if(neightbour.G!=999999){
                        neightbour.G = start.price(min);
                    }
                    neightbour.F = neightbour.H + neightbour.G + neightbour.F;
                    continue;
                }

                // Если клетка уже в открытом списке, то проверяем, 
                //не дешевле ли будет путь через эту клетку. Для сравнения используем стоимость G.
                if (neightbour.G + neightbour.price(min) < min.G) {
                    //Более низкая стоимость G указывает на то, что путь будет дешевле. 
                    //Если это так, то меняем родителя клетки на текущую клетку 
                    neightbour.parent = new Point(min.y, min.x); 
                    neightbour.H = neightbour.mandist(finish);
                    neightbour.G = start.price(min);
                    //и пересчитываем для нее стоимости G и F.
                    neightbour.F = neightbour.H + neightbour.G;
                }
            }

            //Останавливаемся если:
            //Добавили целевую клетку в открытый список, в этом случае путь найден.
            //Или открытый список пуст и мы не дошли до целевой клетки. В этом случае путь отсутствует.

            if (openList.contains(finish)) {
                //finish.parent = openList.getLast();
                finish.parent = closedList.getFirst();
                found = true;
            }else if(openList.isEmpty()){
                return "Z";
            }
        }
        
        //если путь найден, то сохраняем путь, двигаясь назад от целевой точки до стартовой точки
        if (found) {
            Point rd = finish;
            while (!rd.equals(start)) {
                //Если родительская клетка находится сверху, то в нашей системе координат
                if (rd.y+1 == rd.parent.y) {
                    //робот прошел вниз
                    way = way.concat("U");
                }
                else {
                    //Если родительская клетка не сверху, а снизу, то
                    if (rd.y-1 == rd.parent.y) {
                        //Робот прошел вверх
                       way = way.concat("D"); 
                    } 
                    else {
                        //Если родительская клетка не сверху, не снизу, а справа
                        if (rd.x+1 == rd.parent.x) {
                            //то робот прошел налево
                            way = way.concat("L");
                        }
                        else {
                            //Если родительская клетки не сверху, не снизу, не справа, 
                            //Значит она слева и робот прошел вправо
                            way = way.concat("R");
                        }
                    }
                }
               //Ставим родительскую клетку на место проверяемой клетки 
               rd = rd.parent;
               //И если родительская и проверяемая равны, значит дошли до начальной клетки
               if (rd == rd.parent) {
                   break;
               }
            }
        }
        //Инвертируем строку, так как собираем ходы от конца к началу
        StringBuilder buf = new StringBuilder(way);
        way = buf.reverse().toString();
        return way;
    }
    
    /**
     * Проверка на то, убъет ли ход через эту клетку робота (нужна для AStar)
     * @param dir - в какой стороне находится клетка относительно родительской
     * @param par - родительская клетка
     * @param isFirst - будет ли этот ход первым в искомом пути
     * @return умрет робот, идущий в эту клетку или нет
     */
    private boolean checkDeath(Direction dir, Point par, boolean isFirst)
    {
        //Если это не ближайшая к роботу клетка, нас не интересует, может ли туда падать камень
        if(!isFirst){
            return false;
        }
               
        //В случае, если робот идёт вниз
        if((dir==Direction.Down)& area[par.y-1][par.x]==CellType.Stone){
            return true;
        }else{ //В остальных случаях
            //считаем координаты целевой клетки
            Point temp = new Point(par.y, par.x);
            switch(dir){
                case Up:
                    temp.y--;
                    break;
                case Left:
                    temp.x--;
                    break;
                case Right:
                    temp.x++;
                    break;
            }
            if(area[temp.y][temp.x]==CellType.Wall){
                return false;
            }
            //Проверяем, не подпадает ли клетка под условие падения камня.
            //Смотрим, есть ли куда чему-либо падать
            if(area[temp.y-1][temp.x]==CellType.Empty){
                if(area[temp.y-2][temp.x]==CellType.Stone){
                    //Если вверху пустая клетка, а над ней камень, робот умрет
                    return true;
                }else if(area[temp.y-2][temp.x]==CellType.Empty){
                    //Или если сверху две пустые клетки, то проверяем, есть ли камни, падающие вбок
                    if(area[temp.y-1][temp.x+1]==CellType.Stone & area[temp.y-2][temp.x+1]==CellType.Stone){
                        return true;
                    }else if((area[temp.y-1][temp.x-1]==CellType.Stone || area[temp.y-1][temp.x-1]==CellType.A) & area[temp.y-2][temp.x-1]==CellType.Stone){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    /**
     * Убираем собранную лямбду с поля, заменяя ее пустой клеткой
     * @param p точка, в которой собираем лямбду
     */
    public boolean checkL(Point p){
        if (area[p.y][p.x] == CellType.A){
            area[p.y][p.x] = CellType.Ground; 
            return true;
        }
        else{
            return false;
        }
    }
    /**
     * Заменяем землю пустотой (после прохода робота)
     * @param p точка, в которой собираем лямбду
     */
    public void cleanGround(Point p){
        if (area[p.y][p.x] == CellType.Ground){
            area[p.y][p.x] = CellType.Empty; 
        }
    }
    /**
     * @param p - точка с координатами x, y
     * @return тип ячейки, находящейся по координатам x, y
     */
    public CellType getCell(Point p){
        return area[p.y][p.x];
    };
    /**
     * Случай, когда робот может сдвинуть камень
     * @param pos - клетка, в которую мы двигаемся
     * @param dir - направление движения
     * @return true - если движение возможно (и камень уже сдвинут)
     * @return false - в обратном случае.
     */
    public boolean robotMovesStone(Point pos, Direction dir){
        //Если в клетке камень
        if(area[pos.y][pos.x]==CellType.Stone){
            //И двигаемся влево
            if(dir==Direction.Left){
                //И за камнем пусто
                if(area[pos.y][pos.x-1]==CellType.Empty){
                    //Двигаем камень влево
                    area[pos.y][pos.x]=CellType.Ground;
                    area[pos.y][pos.x-1]=CellType.Stone;
                    return true;
                }
                    
            }else if(dir==Direction.Right){ //или мы двигемся вправо
                //И за камнем пусто
                if(area[pos.y][pos.x+1]==CellType.Empty){
                    //Двигаем камень вправо
                    area[pos.y][pos.x]=CellType.Ground;
                    area[pos.y][pos.x+1]=CellType.Stone;
                    return true;
                }
            }
        }
        return false;
    };
    
    /**
     * Шаг симуляции (движение камней)
     * @return true/false - умер робот, или нет
     */
    public boolean step(Point robot){
        for(int j=height-1; j>=0; j--){
            for(int i = 0; i<width; i++){
                //Нашли камень
               if(area[j][i]==CellType.Stone){
                   //Проверили, не должен ли упасть камень
                   Point p = checkStone(j, i);
                   //Если камень падает
                   if (p.y!=0) {
                       //Перемещаем камень
                       area[j][i]=CellType.Empty;
                       area[p.y][p.x]=CellType.Stone;
                       //Проверяем, не на робота ли упал камень
                       if (robot.y==j+2 & robot.x==i){
                           return true;
                       }
                   }
               }
            }
       }
       return false;
    };
    /**
     * Проверяем, может ли упасть камень, и если может, то передвигаем.
     * @param y координата камня
     * @param x координата камня
     * @return (0,0) если камень не падает, или ненулевую точку, в которую упал камень
     */
    private Point checkStone(int y, int x)
    {
        //Если снизу пусто
        if (area[y+1][x]==CellType.Empty){
            return new Point(y+1,x);
        } 
        //Если внизу камень, снизу справа и справа пусто
        else if (area[y+1][x]==CellType.Stone){
                if (area[y+1][x+1]==CellType.Empty & area[y][x+1]==CellType.Empty){
                    return new Point(y+1,x+1);
                } 
                else 
                    //Если слева и снизу слева пусто
                    if (area[y+1][x-1]==CellType.Empty & area[y][x-1]==CellType.Empty){
                    return new Point(y+1,x-1);
                }
        }
        else 
            //Если снизу лямбда и справа и справа снизу пусто
            if(area[y+1][x]==CellType.A & area[y+1][x+1]==CellType.Empty & area[y][x+1]==CellType.Empty){
                return new Point(y+1,x+1);
            }
            return new Point(0,0);
    }
    /**
     * Заменяет клетку Close на клетку Open
     */
    public void openExit(){
        area[exit.y][exit.x]=CellType.Open;
    };
};
